import bisect                                   #二分查找库函数
def makeArrayIncreasing(arr1, arr2):
        # 预处理：排序，去重，加哨兵
        maxv = 999999
        arr1 = [-1] + arr1 + [maxv + 5]
        arr2 = sorted(list(set(arr2)))
        n = len(arr1)

        dp = [0] + [maxv]*(n-1)
        for i in range(1,n):
            j = bisect.bisect_left(arr2, arr1[i])
            for k in range(1, min(i-1, j) + 1):  # 枚举替换的个数 k = 1 to min(i-1,j)
                if arr1[i-k-1] < arr2[j-k]:
                    dp[i] = min(dp[i], dp[i-k-1] + k)
            if arr1[i-1] < arr1[i]:              # 不替换 arr1[i-1]
                dp[i] = min(dp[i], dp[i-1])
        return dp[-1] if dp[-1] < maxv else -1

#算法测试
if __name__ == '__main__':
    arr1=[1,5,3,6,7]
    arr2=[4,3,1]
    print(makeArrayIncreasing(arr1,arr2))